/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2024-10-12
 * Time: 21:28
 */
public class Sort {
    public static void quickSort(int[] array) {
        qucik(array, 0, array.length-1);
    }

    private static void qucik(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int pivot = partition(array, start, end);
        qucik(array, start, pivot - 1);
        qucik(array, pivot + 1, end);
    }

    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];

        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];

            while(left < right && array[left] <= tmp){
                left++;
            }
            array[right] = array[left];
        }

        array[left] = tmp;
        return left;
    }

}
